home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / DCLAP 6d / dclap6d / SeqPups / appsrc / cap.src / CAP2.doc < prev    next >
Text File  |  1996-07-05  |  7KB  |  172 lines
  1. /* CONTIG ASSEMBLY PROGRAM (CAP)
  2.  
  3.    copyright (c) 1991    Xiaoqiu Huang
  4.    The distribution of the program is granted provided no charge
  5.    is made and the copyright notice is included.
  6.  
  7.    Proper attribution of the author as the source of the software
  8.    would be appreciated:
  9.    "A Contig Assembly Program Based on Sensitive Detection of
  10.    Fragment Overlaps" (submitted to Genomics, 1991)
  11.     Xiaoqiu Huang
  12.     Department of Computer Science
  13.     Michigan Technological University
  14.     Houghton, MI 49931
  15.         E-mail: huang@cs.mtu.edu
  16.  
  17. ------
  18. call format now is:
  19.     CAP2  file_of_fragments output_file  MIN_OVERLAP PERCENT_MATCH
  20.  
  21. where:
  22.     file_of_fragments -- input data, in pearson/fasta format
  23.     output_file                -- output data, in fasta format
  24.     MIN_OVERLAP;           -- Minimum length of any overlap  
  25.     PERCENT_MATCH;      -- Minimum identity percentage of any overlap  
  26.                             (give percent as whole number relative to 100)
  27. -------
  28.  
  29.    The CAP program uses a dynamic programming algorithm to compute
  30.    the maximal-scoring overlapping alignment between two fragments.
  31.    Fragments in random orientations are assembled into contigs by a
  32.    greedy approach in order of the overlap scores. CAP is efficient
  33.    in computer memory: a large number of arbitrarily long fragments
  34.    can be assembled. The time requirement is acceptable; for example,
  35.    CAP took 4 hours to assemble 1015 fragments of a total of 252 kb
  36.    nucleotides on a Sun SPARCstation SLC. The program is written in C
  37.    and runs on Sun workstations.
  38.  
  39.    Below is a description of the parameters in the #define section of CAP.
  40.    Two specially chosen sets of substitution scores and indel penalties
  41.    are used by the dynamic programming algorithm: heavy set for regions
  42.    of low sequencing error rates and light set for fragment ends of high
  43.    sequencing error rates. (Use integers only.)
  44.     Heavy set:             Light set:
  45.  
  46.     MATCH     =  2             MATCH     =  2
  47.     MISMAT    = -6             LTMISM    = -3
  48.     EXTEND    =  4             LTEXTEN   =  2
  49.  
  50.     In the initial assembly, any overlap must be of length at least OVERLEN,
  51.     and any overlap/containment must be of identity percentage at least
  52.     PERCENT. After the initial assembly, the program attempts to join
  53.     contigs together using weak overlaps. Two contigs are merged if the
  54.     score of the overlapping alignment is at least CUTOFF. The value for
  55.     CUTOFF is chosen according to the value for MATCH.
  56.  
  57.     DELTA is a parameter in necessary conditions for overlap/containment.
  58.     Those conditions are used to quickly reject pairs of fragments that
  59.     could not possibly have an overlap/containment relationship.
  60.     The dynamic programming algorithm is only applied to pairs of fragments
  61.     that pass the screening. A large value for DELTA means stringent
  62.     conditions, where the value for DELTA is a real number at least 8.0.
  63.  
  64.     POS5 and POS3 are fragment positions such that the 5' end between base 1
  65.     and base POS5, and the 3' end after base POS3 are of high sequencing
  66.     error rates, say more than 5%. For mismatches and indels occurring in
  67.     the two ends, light penalties are used.
  68.  
  69.     A file of input fragments looks like:
  70. >G019uabh
  71. ATACATCATAACACTACTTCCTACCCATAAGCTCCTTTTAACTTGTTAAA
  72. GTCTTGCTTGAATTAAAGACTTGTTTAAACACAAAAATTTAGAGTTTTAC
  73. TCAACAAAAGTGATTGATTGATTGATTGATTGATTGATGGTTTACAGTAG
  74. GACTTCATTCTAGTCATTATAGCTGCTGGCAGTATAACTGGCCAGCCTTT
  75. AATACATTGCTGCTTAGAGTCAAAGCATGTACTTAGAGTTGGTATGATTT
  76. ATCTTTTTGGTCTTCTATAGCCTCCTTCCCCATCCCCATCAGTCTTAATC
  77. AGTCTTGTTACGTTATGACTAATCTTTGGGGATTGTGCAGAATGTTATTT
  78. TAGATAAGCAAAACGAGCAAAATGGGGAGTTACTTATATTTCTTTAAAGC
  79. >G028uaah
  80. CATAAGCTCCTTTTAACTTGTTAAAGTCTTGCTTGAATTAAAGACTTGTT
  81. TAAACACAAAATTTAGACTTTTACTCAACAAAAGTGATTGATTGATTGAT
  82. TGATTGATTGATGGTTTACAGTAGGACTTCATTCTAGTCATTATAGCTGC
  83. TGGCAGTATAACTGGCCAGCCTTTAATACATTGCTGCTTAGAGTCAAAGC
  84. ATGTACTTAGAGTTGGTATGATTTATCTTTTTGGTCTTCTATAGCCTCCT
  85. TCCCCATCCCATCAGTCT
  86. >G022uabh
  87. TATTTTAGAGACCCAAGTTTTTGACCTTTTCCATGTTTACATCAATCCTG
  88. TAGGTGATTGGGCAGCCATTTAAGTATTATTATAGACATTTTCACTATCC
  89. CATTAAAACCCTTTATGCCCATACATCATAACACTACTTCCTACCCATAA
  90. GCTCCTTTTAACTTGTTAAAGTCTTGCTTGAATTAAAGACTTGTTTAAAC
  91. ACAAAATTTAGACTTTTACTCAACAAAAGTGATTGATTGATTGATTGATT
  92. GATTGAT
  93. >G023uabh
  94. AATAAATACCAAAAAAATAGTATATCTACATAGAATTTCACATAAAATAA
  95. ACTGTTTTCTATGTGAAAATTAACCTAAAAATATGCTTTGCTTATGTTTA
  96. AGATGTCATGCTTTTTATCAGTTGAGGAGTTCAGCTTAATAATCCTCTAC
  97. GATCTTAAACAAATAGGAAAAAAACTAAAAGTAGAAAATGGAAATAAAAT
  98. GTCAAAGCATTTCTACCACTCAGAATTGATCTTATAACATGAAATGCTTT
  99. TTAAAAGAAAATATTAAAGTTAAACTCCCCTATTTTGCTCGTTTTTGCTT
  100. ATCTAAAATACATTCTGCACAATCCCCAAAGATTGATCATACGTTAC
  101. >G006uaah
  102. ACATAAAATAAACTGTTTTCTATGTGAAAATTAACCTANNATATGCTTTG
  103. CTTATGTTTAAGATGTCATGCTTTTTATCAGTTGAGGAGTTCAGCTTAAT
  104. AATCCTCTAAGATCTTAAACAAATAGGAAAAAAACTAAAAGTAGAAAATG
  105. GAAATAAAATGTCAAAGCATTTCTACCACTCAGAATTGATCTTATAACAT
  106. GAAATGCTTTTTAAAAGAAAATATTAAAGTTAAACTCCCC
  107.    A string after ">" is the name of the following fragment.
  108.    Only the five upper-case letters A, C, G, T and N are allowed
  109.    to appear in fragment data. No other characters are allowed.
  110.    A common mistake is the use of lower case letters in a fragment.
  111.  
  112.    To run the program, type a command of form
  113.  
  114.     cap  file_of_fragments  
  115.  
  116.    The output goes to the terminal screen. So redirection of the
  117.    output into a file is necessary. The output consists of three parts:
  118.    overview of contigs at fragment level, detailed display of contigs
  119.    at nucleotide level, and consensus sequences.
  120.    '+' = direct orientation; '-' = reverse complement
  121.    The output of CAP on the sample input data looks like:
  122.  
  123. #Contig 1
  124.  
  125. #G022uabh+(0)
  126. TATTTTAGAGACCCAAGTTTTTGACCTTTTCCATGTTTACATCAATCCTGTAGGTGATTG
  127. GGCAGCCATTTAAGTATTATTATAGACATTTTCACTATCCCATTAAAACCCTTTATGCCC
  128. ATACATCATAACACTACTTCCTACCCATAAGCTCCTTTTAACTTGTTAAAGTCTTGCTTG
  129. AATTAAAGACTTGTTTAAACACAAAA-TTTAGACTTTTACTCAACAAAAGTGATTGATTG
  130. ATTGATTGATTGATTGAT
  131. #G028uaah+(145)
  132. CATAAGCTCCTTTTAACTTGTTAAAGTCTTGCTTGAATTAAAGACTTGTTTAAACACAAA
  133. A-TTTAGACTTTTACTCAACAAAAGTGATTGATTGATTGATTGATTGATTGATGGTTTAC
  134. AGTAGGACTTCATTCTAGTCATTATAGCTGCTGGCAGTATAACTGGCCAGCCTTTAATAC
  135. ATTGCTGCTTAGAGTCAAAGCATGTACTTAGAGTTGGTATGATTTATCTTTTTGGTCTTC
  136. TATAGCCTCCTTCCCCATCCC-ATCAGTCT
  137. #G019uabh+(120)
  138. ATACATCATAACACTACTTCCTACCCATAAGCTCCTTTTAACTTGTTAAAGTCTTGCTTG
  139. AATTAAAGACTTGTTTAAACACAAAAATTTAGAGTTTTACTCAACAAAAGTGATTGATTG
  140. ATTGATTGATTGATTGATGGTTTACAGTAGGACTTCATTCTAGTCATTATAGCTGCTGGC
  141. AGTATAACTGGCCAGCCTTTAATACATTGCTGCTTAGAGTCAAAGCATGTACTTAGAGTT
  142. GGTATGATTTATCTTTTTGGTCTTCTATAGCCTCCTTCCCCATCCCCATCAGTCTTAATC
  143. AGTCTTGTTACGTTATGACT-AATCTTTGGGGATTGTGCAGAATGTTATTTTAGATAAGC
  144. AAAA-CGAGCAAAAT-GGGGAGTT-A-CTT-A-TATTT-CTTT-AAA--GC
  145. #G023uabh-(426)
  146. GTAACGT-ATGA-TCAATCTTTGGGGATTGTGCAGAATGT-ATTTTAGATAAGCAAAAAC
  147. GAGCAAAATAGGGGAGTTTAACTTTAATATTTTCTTTTAAAAAGCATTTCATGTTATAAG
  148. ATCAATTCTGAGTGGTAGAAATGCTTTGACATTTTATTTCCATTTTCTACTTTTAGTTTT
  149. TTTCCTATTTGTTTAAGATCGTAGAGGATTATTAAGCTGAACTCCTCAACTGATAAAAAG
  150. CATGACATCTTAAACATAAGCAAAGCATATTTTTAGGTTAATTTTCACATAGAAAACAGT
  151. TTATTTTATGTGAAATTCTATGTAGATATACTATTTTTTTGGTATTTATT
  152. #G006uaah-(496)
  153. GGGGAGTTTAACTTTAATATTTTCTTTTAAAAAGCATTTCATGTTATAAGATCAATTCTG
  154. AGTGGTAGAAATGCTTTGACATTTTATTTCCATTTTCTACTTTTAGTTTTTTTCCTATTT
  155. GTTTAAGATCTTAGAGGATTATTAAGCTGAACTCCTCAACTGATAAAAAGCATGACATCT
  156. TAAACATAAGCAAAGCATATNNT-AGGTTAATTTTCACATAGAAAACAGTTTATTTTATG
  157. T
  158.  
  159.  
  160.  
  161. Slight modifications by S. Smith on Mon Feb 17 10:18:34 EST 1992.
  162. These changes allow for command line arguements for several
  163. of the hard coded parameters, as well as a slight modification to
  164. the output routine to support GDE format.  Changes are commented
  165. as:
  166.  
  167. Mod by S.S.
  168.  
  169.  
  170. more mods for use with Macintosh SeqApp program, d.g. gilbert, June 93
  171. */
  172.